package PTA.练习04;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-11-15
 * Time: 21:53
 */
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int MaxSize = sc.nextInt();//最大的容量
        MinHeap h = new MinHeap(MaxSize);
        int[] list= new int[MaxSize];
        for (int i = 0; i < MaxSize; i++) {
            list[i] = sc.nextInt();
        }
        h.create(list);
        int DeletTime = sc.nextInt();
        for (int i = 0; i < DeletTime; i++) {
            int x=h.pop();
            System.out.println(x);
        }
        int InsertTime = sc.nextInt();//插入元素的个数
        for (int i = 0; i < InsertTime; i++) {
            int element = sc.nextInt();//插入的元素
            h.insert(element);
        }
        System.out.println(h.pop());
    }
}
class MinHeap{
    int capacity=0;
    int size=0;
    int[] heap;
    //创建一个容量为capacity的最小堆
    public MinHeap(int capacity){
        this.capacity=capacity;
        heap=new int[capacity];
    }
    // 交换堆中两个元素的位置
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 上浮操作
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[index] < heap[parentIndex]) {
                swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 下沉操作
    private void heapifyDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallest = index;

        if (leftChildIndex < size && heap[leftChildIndex] < heap[smallest]) {
            smallest = leftChildIndex;
        }

        if (rightChildIndex < size && heap[rightChildIndex] < heap[smallest]) {
            smallest = rightChildIndex;
        }

        if (smallest != index) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }

    //利用给定的数组list创建一个最小堆,若list的长度超过容量，则输出数组过长
    public void create(int[] list){
        if (list.length>capacity){
            System.out.println("数组过长");
            return;
        }
        for (int i = 0; i < list.length; i++) {
            heap[size]=list[i];
            heapifyUp(size);
            size++;
        }
    }

    //判断该最小堆是否已满
    public boolean isFull(){
        return size==capacity;
    }

    //判断该最小堆是否为空
    public boolean isEmpty(){
        return size==0;
    }

    //在最小堆中插入1个值为e的元素,若插入前堆满则输出The heap is full
    public boolean insert(int e){
        if(isFull()){
            System.out.println("The heap is full");
            return false;
        }
        heap[size]=e;
        heapifyUp(size);
        size++;
        return true;
    }

    //抛出最小堆的最小值（同时删除这个元素，若抛出前堆空则输出The heap is empty并返回-1
    public int pop(){
        if (isEmpty()){
            System.out.println("The heap is empty");
            return -1;
        }
        int min=heap[0];
        heap[0]=heap[size-1];
        heapifyDown(0);
        size--;
        return min;
    }
}
